<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>图（无向图）结构的封装</title>
</head>
<body>
<script src="dict.js"></script>
<script src="queue.js"></script>
<script>
    function Graph() {
        this.vertexes = []; //顶点
        this.edges = new Dictionary(); //边

        /*方法*/
        // 1.添加顶点的方法
        Graph.prototype.addVertexes = function (v) {
            this.vertexes.push(v);
            this.edges.set(v, []); //顶点刚添加进来时没有边，所有先给个空数组
        };

        /**
         * 在两个顶点之间添加一条边
         * @param v1
         * @param v2
         */
        Graph.prototype.addEdge = function (v1, v2) {
            this.edges.get(v1).push(v2);
            this.edges.get(v2).push(v1);
        };

        Graph.prototype.toString = function () {
            let resultString = "";

            // 遍历所有的顶点，以及顶点对应的边
            for (let i = 0; i < this.vertexes.length; i++) {
                const v = this.vertexes[i];
                resultString += v + '->';
                const vEdges = this.edges.get(v);
                for (const e of vEdges) { //循环顶点对应的边
                    resultString += e + ' ';
                }
                resultString += '\n'; //每打印一个顶点和其对应边就换行
            }
            return resultString;
        };

        //初始化顶点的颜色状态
        Graph.prototype.initializeColor = function () {
            let colors = [];
            for (const i of this.vertexes) {
                colors[i] = 'white'; //顶点的颜色状态初始为白色
            }
            return colors;
        };

        /**
         * 实现广度优先搜索(BFS)
         * @param firstV 从哪个顶点开始
         * @param handler 传入的函数
         */
        Graph.prototype.bfs = function (firstV, handler) {
            // 1.初始化颜色
            let colors = this.initializeColor();

            // 2. 创建队列
            let queue = new Queue();

            // 3.将顶点加入队列
            queue.enqueue(firstV);

            // 4.循环从队列中取出元素
            while (!queue.isEmpty()) {
                // 4.1从队列中取出第一个顶点
                let v = queue.dequeue();

                 // 4.2获取和该顶点相连的顶点
                let vList = this.edges.get(v);

                // 4.3将v的颜色设置成灰色
                colors[v] = 'gray';

                // 4.4遍历所有相连的顶点，并且加入到队列中
                for (const v of vList) {
                    if (colors[v] === 'white') { //颜色状态为白色(未访问未探索)才加入队列
                        colors[v] = 'gray'; //顶点颜色状态改为灰色(已访问未探索)
                        queue.enqueue(v);
                    }
                }

                // 4.5调用回到函数将顶点返回出去
                handler(v);

                // 4.6次顶点被探索，设置为黑色
                colors[v] = 'black'
            }
        };

        /**
         * 深度优先遍历(DFS)
         * @param firstV
         * @param handler
         */
        Graph.prototype.dfs = function (firstV, handler) {
            // 1.初始化颜色
            let colors = this.initializeColor();

            // 2.从某个顶点开始依次递归访问
            this.dfsVisit(firstV, colors, handler);
        };

        Graph.prototype.dfsVisit = function (v, colors, handler) {
            // 1.将颜色设置为灰色
            colors[v] = 'gary';

            // 2.执行回调函数(处理v顶点)
            handler(v);

            // 3.访问v相连的顶点
            let vList = this.edges.get(v);
            for (const v of vList) {
                if (colors[v] === 'white') { //为被访问过则进行访问
                    this.dfsVisit(v, colors, handler)
                }
            }

            // 4.顶点已被探索，设置为黑色
            colors[v] = 'black';
        }

        

    }

</script>
<script>
    //测试代码
    let graph = new Graph();

    //添加顶点
    let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
    for (const i of myVertexes) {
        graph.addVertexes(i);
    }

    //添加边
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('A', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'G');
    graph.addEdge('D', 'G');
    graph.addEdge('D', 'H');
    graph.addEdge('B', 'E');
    graph.addEdge('B', 'F');
    graph.addEdge('E', 'I');

    console.log(graph.toString());

    // 测试bfs遍历
    let result = '';
    graph.bfs('A', v => {
        result += v + ' ';
    });
    console.log(result);

    // 测试bfs遍历
    let dfsResult = '';
    graph.dfs('A', v => {
        dfsResult += v + ' ';
    });
    console.log(dfsResult);
</script>
</body>
</html>